# 思路：慢指针每次走一步，快指针每次走两步，当快指针走到头，慢指针刚好到回文开始的位置(或-1)
# 将后续的链表反转，快指针重新指向head，此时快指针和慢指针每次走一步，对比两个值，值相等则继续，否则返回False
from tools.listNode import listToNode


class Solution(object):

    def isPalindrome(self, head):
        if not head or not head.next:
            return True
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        if fast:
            slow = slow.next
        fast = head
        reversed_list = self.reverseList(slow)
        while reversed_list:
            if fast.val != reversed_list.val:
                return False
            fast = fast.next
            reversed_list = reversed_list.next
        return True

    # 反转链表
    def reverseList(self, head):
        cur = head
        prev = None
        while cur:
            next_node = cur.next
            cur.next = prev
            prev = cur
            cur = next_node
        return prev


print(Solution().isPalindrome(listToNode([1, 2, 3])))
print(Solution().isPalindrome(listToNode([1, 2, 2, 1])))
print(Solution().isPalindrome(listToNode([1, 2, 1])))
